package dynamic;

/**
 * 矩阵相乘
 * @author lenovo
 *
 */
public class MatixChain {

	public static final int SIZE = 4;
	int n = SIZE;
	String[] m = { "", "A", "B", "C", "D" };
	int[] p = { 30, 1, 40, 10, 25 }; //每个矩阵的行和列
	int[][] f = new int[n + 1][n + 1];
	int[][] a = new int[n + 1][n + 1];

	void dynamic() {
		for (int len = 1; len <= n - 1; len++) {
			for (int i = 1; i <= n - len; i++) {
				int j = i + len;
				//f[i][j]
				int min = Integer.MAX_VALUE;
				int mink = Integer.MAX_VALUE;
				for (int k = i; k < j; k++) {
					int temp = f[i][k] + f[k + 1][j] + p[i-1] * p[k] * p[j];
					if (temp < min) {
						min = temp;
						mink = k;
					}
				}
				f[i][j] = min;
				a[i][j] = mink;
			}
		}
	}

	void output() {
		System.out.println("output:" + f[1][n]);
		outputA(1, n);
	}

	void outputA(int i, int j) {
		if (i == j) {
			System.out.print(m[i]);
			return;
		}
		int k = a[i][j];
		System.out.print("(");
		outputA(i, k);
		//System.out.print(")");
		//System.out.print("(");
		outputA(k + 1, j);
		System.out.print(")");
	}

	public static void main(String[] args) {
		MatixChain mc = new MatixChain();
		mc.dynamic();
		mc.output();
	}
}
